package november.sort;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/11/18-21:27
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }

//        int[] arr = {2,5,6,1,123,9,1,12,7};
        long timeMillis1 = System.currentTimeMillis();

        shellSort(arr);
        long timeMillis2 = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(timeMillis2 - timeMillis1);
    }

    private static void shellSort(int[] arr) {
//        int gap = arr.length;
        int insertIndex;
        int insertValue;
        //分成gap组
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //无序表
                insertIndex = i - gap;//插入的坐标(有序表最后一个)
                insertValue = arr[i];//待插入的数(无序表第一个)
                //无序表与(有序表元素从尾到头)进行比较 , 直到找到比无序表第一个元素小的 有序表元素
                if (arr[insertIndex] > insertValue) { //有序表最后一个元素>无序表第一个元素 ,循环才有意义
                    while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                        //比较的同时也进行元素后移
                        arr[insertIndex + gap] = arr[insertIndex];
                        insertIndex -= gap;
                    }
                    if (insertIndex + gap != i) {
                        //找到要插入的位置进行插入
                        arr[insertIndex + gap] = insertValue;
                    }
                }
            }
        }

    }

    private static void shellSort2(int[] arr) {
//        int gap = arr.length;
        int insertIndex;
        int insertValue;
        int gap = arr.length / 2;
        while (true) {
            for (int i = gap; i < arr.length; i++) {
                //无序表
                insertIndex = i - gap;//插入的坐标(有序表最后一个)
                insertValue = arr[i];//待插入的数(无序表第一个)
                //无序表与(有序表元素从尾到头)进行比较 , 直到找到比无序表第一个元素小的 有序表元素
                if (arr[insertIndex] > insertValue) { //有序表最后一个元素>无序表第一个元素 ,循环才有意义
                    while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                        //比较的同时也进行元素后移
                        arr[insertIndex + gap] = arr[insertIndex];
                        insertIndex -= gap;
                    }
                    if (insertIndex + gap != i) {
                        //找到要插入的位置进行插入
                        arr[insertIndex + gap] = insertValue;
                    }
                }
            }

            if (gap == 1) {
                break;
            }
            gap = gap / 2;
        }
    }
}
